/*
 * DijkstraShortestPath.cpp
 *
 *  Created on: Sep 25, 2009
 *      Author: jbarreneche
 */

#include "DijkstraShortestPath.h"
#include "VisitedVertexInfo.h"
#include "exceptions/OutOfReachException.h"
#include "CheaperMatcher.h"
#include "core/path/MatcherInInfo.h"
#include <stdio.h>

using namespace util;

namespace path {
// Recorre una lista de VisitedVertexInfo y extrae el que posee menor costo
VisitedVertexInfo* pickCheaper(LinkedList<VisitedVertexInfo*> &vertices);
// Arma un Path a partir del previousVertexInfo de cada VisitedVertexInfo
// hasta llegar al de inicio
Path* retracePath(VisitedVertexInfo* currentVertex);

DijkstraShortestPath::DijkstraShortestPath(EdgeCost* edgeCost) {
	this->edgeCost = edgeCost;
}

DijkstraShortestPath::~DijkstraShortestPath() {
	delete this->edgeCost;
}

Path* DijkstraShortestPath::solvePath(Vertex* origin, Vertex* destiny,
		LinkedList<Vertex*> &vertices, LinkedList<Edge*> &edges)
		throw (OutOfReachException) {

	LinkedList<Edge*> pendingEdges;
	LinkedList<VisitedVertexInfo*> visitedVertices;
	LinkedList<VisitedVertexInfo*> availableVertices;
	MatcherInInfo vertexMatcher;

	// push current origin as the only available vertex
	VisitedVertexInfo* currentVertex = new VisitedVertexInfo(origin);
	availableVertices.append(currentVertex);

	while (!availableVertices.isEmpty()) {
		// pick cheaper vertex
		currentVertex = pickCheaper(availableVertices);
		// if is destination break (because negative edges aren't allowed)
		if (currentVertex->getRealVertex()->equals(destiny))
			break;
		// push all edges from current vertex
		pendingEdges.pushAll(currentVertex->getRealVertex()->getOutgoingEdges());

		// Iterate all edges and update vertex that haven't been visited
		while (!pendingEdges.isEmpty()) {
			// pop an Edge
			Edge* transversing = pendingEdges.removeFirst();
			Vertex* destination = transversing->getDestination();
			// if hasn't been visited
			if (!visitedVertices.contains(vertexMatcher.setCurrent(destination))) {
				try {
					// search for it in the available list
					VisitedVertexInfo* destinationInfo =
							availableVertices.search(&vertexMatcher);
					// update it in available
					destinationInfo->updateInfo(currentVertex->getReachCost() + this->edgeCost->cost(*transversing),
							currentVertex, transversing);
				} catch (ElementNotFoundException e) {
					// if isn't in available add it to available
					VisitedVertexInfo* destinationInfo = new VisitedVertexInfo(
							destination, currentVertex->getReachCost()
									+ this->edgeCost->cost(*transversing),
							currentVertex, transversing);
					availableVertices.add(0, destinationInfo);
				}
			}
		}
		// add current vertex to the list of visited vertices
		visitedVertices.add(0, currentVertex);
	}
	if (!(currentVertex->getRealVertex()->equals(destiny)))
		throw OutOfReachException(
				"No se pudo encontrar un camino entre el origen y el destino");

	Path* resultPath = retracePath(currentVertex);
	return resultPath;
}
double DijkstraShortestPath::cost(Edge* edge) {
	return this->getEdgeCost()->cost(*edge);
}

// Recursivo para que el path se arme en el orden correcto
Path* retracePath(Path* resultPath, VisitedVertexInfo* currentVertex) {
	if (currentVertex->getReachedFrom() != NULL) {
		return retracePath(resultPath,
				currentVertex->getReachedFrom())->append(currentVertex->getReachedThrough());
	}
	return resultPath;
}

Path* retracePath(VisitedVertexInfo* currentVertex) {
	Path* resultPath = new Path();
	return retracePath(resultPath, currentVertex);
}

VisitedVertexInfo* pickCheaper(LinkedList<VisitedVertexInfo*> &vertices) {
	CheaperMatcher matcher;
	vertices.contains(&matcher);
	vertices.remove(matcher.getCheaperPosition());
	return matcher.getCheaper();
}

EdgeCost* DijkstraShortestPath::getEdgeCost() {
	return this->edgeCost;
}

}
